package com.example.algo.lengthOfLongestSubstring;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 无重复字符的最长子串
 * 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
 * <p>
 * 示例 1:
 * <p>
 * 输入: "abcabcbb"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 * 示例 2:
 * <p>
 * 输入: "bbbbb"
 * 输出: 1
 * 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
 * 示例 3:
 * <p>
 * 输入: "pwwkew"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
 *      请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
 * <p>
 * 来源：力扣（LeetCode）
 *
 * @author zhoubin
 * @date 2019-06-21 14:05:28
 */
public class Solution {


    public static void main(String[] args) {

        String str = "abcbbfedcbagbddddb";
        System.out.println(lengthOfLongestSubstring(str));
        System.out.println(lengthOfLongestSubstring1(str));
        System.out.println(lengthOfLongestSubstring2(str));
    }

    /**
     * 循环 2n 遍
     * 时间复杂度 O(2n)=O(n) 最糟糕的情况下，每个字符将被 start 和 end 访问两次。
     * 空间复杂度 O(min(m, n))，与之前的方法相同。滑动窗口法需要 O(k) 的空间
     * 其中 k 表示 Set 的大小，而 Set 的大小取决于字符串 n 的大小以及字符集字母 m 的大小
     *
     * @param s
     * @return
     */
    public static int lengthOfLongestSubstring1(String s) {
        int n = s.length();
        // 获取最长不同字符串的起始下标
        int ansStartIndex = 0;
        // ans 最长字符串长度, start 滑动窗口左边界 end 滑动窗口右边界
        int ans = 0, start = 0, end = 0;
        Set<Character> set = new HashSet<>();
        while (start < n && end < n) {
            char charAt_end_value = s.charAt(end);
            if (!set.contains(charAt_end_value)) {
                char charAt_end_next_value = s.charAt(end++);
                set.add(charAt_end_next_value);
                // 不获取字符串的时候可以用Math.max()函数获取长度
//                ans = Math.max(ans, end - start);

                // 计算 ans 的长度和起始下标的位置
                if (ans < end - start) {
                    ans = end - start;
                    ansStartIndex = start;
                }
            } else {
                char charAt_start_next_value = s.charAt(start++);
                set.remove(charAt_start_next_value);
            }
        }

        // 获取重复的字符串
        System.out.println(s.substring(ansStartIndex, ansStartIndex + ans));
        return ans;
    }

    /**
     * 优化 只循环 n 遍
     * 时间复杂度 O(n) 窗口右边界 end 将会迭代 n 次
     * 空间复杂度 O(min(m, n)), 一般是字符串中最多不重复的字符个数
     *
     * @param s
     * @return
     */
    public static int lengthOfLongestSubstring2(String s) {
        int n = s.length();
        // 获取最长不同字符串的起始下标
        int ansStartIndex = 0;
        // ans 最长字符串长度, start 滑动窗口左边界 end 滑动窗口右边界
        int ans = 0, start = 0, end = 0;
        // map 存放重复字符串最后一个重复的下标
        Map<Character, Integer> map = new HashMap<>();
        for (; end < n; end++) {
            // 方便调试声明的变量
            char charAt_end_value = s.charAt(end);
            if (map.containsKey(charAt_end_value)) {
                // 方便调试声明的变量
                int charAt_end_index = map.get(charAt_end_value);
                start = Math.max(charAt_end_index, start);
            }

            // 不获取字符串的时候可以用Math.max()函数获取长度
//            ans = Math.max(ans, end - start + 1);
            // 计算 ans 的长度和起始下标的位置
            if (ans < end - start + 1) {
                ans = end - start + 1;
                ansStartIndex = end - ans + 1;
            }
            map.put(charAt_end_value, end + 1);
        }

        // 获取重复的字符串
        System.out.println(s.substring(ansStartIndex, ansStartIndex + ans));
        return ans;
    }

    /**
     * 最优解决方案，当知道字符串所使用的字符集的情况
     * 当我们知道该字符集比较小的时侯，我们可以用一个整数数组作为直接访问表来替换 map
     * 常用的表如下
     * int[26] 用于字母 ‘a’ - ‘z’ 或 ‘A’ - ‘Z’
     * int[128] 用于ASCII码
     * int[256] 用于扩展ASCII码
     *
     * 时间复杂度 O(n) 窗口右边界 end 将会迭代 n 次
     * 空间复杂度 O(m) m 是字符集的大小
     *
     * @param s
     * @return
     */
    public static int lengthOfLongestSubstring(String s) {
        int ansStartIndex = 0;
        int n = s.length(), ans = 0;
        // 当前字符对应的下标
        int[] index = new int[128];

        for (int end = 0, start = 0; end < n; end++) {
            start = Math.max(index[s.charAt(end)], start);
            // 不获取字符串的时候可以用Math.max()函数获取长度
//            ans = Math.max(ans, end - start + 1);

            // 计算 ans 的长度和起始下标的位置
            if (ans < end - start + 1) {
                ans = end - start + 1;
                ansStartIndex = end - ans + 1;
            }
            index[s.charAt(end)] = end + 1;
        }

        // 获取重复的字符串
        System.out.println(s.substring(ansStartIndex, ansStartIndex + ans));
        return ans;
    }


}
